Masala #0475

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 45 %

2.6 (Baholar 5)

ab satr

Sizga faqatgina ‘a’, ‘b’ va ‘?’ dan tashkil topgan S satr beriladi. Bu yerda ‘?’ belgisi ‘a’ yoki ‘b’ ekanligini ifodalaydi. Shunday ekan satrda jami k ta ‘?’ belgisi mavjud bo’lsa ‘?’ lar o’rniga ‘a’ yoki ‘b’ ni qo’yish variantlar soni 2k tani tashkil etadi. Siz barcha variantlar uchun (i < j and Si = ‘b’ and Sj = ‘a’) shartni qanoatlantiradigan (i, j) juftliklar sonining umumiy summasini toping.

Kiruvchi ma'lumotlar:

Kirish faylida yagona satr, $S (1 \le |S| \le 500000)$ satri kiritiladi.

Chiquvchi ma'lumotlar:

Sizdan so’ralgan natijani $1000000007 (10^9+7)$ ga bo’lgandagi qoldiqni chop eting.

Misollar

#	input.txt	output.txt
1	ababa	3
2	b??	5
3	a?b????a	256

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin